// ALERT: 本代码中涉及的树,一定是按层次建立的二叉树。

#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;
typedef struct BSTNode {
	KeyType key;
	struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;


// FUNCTION: 向二叉排序树中插入元素（递归方式实现）
// HINT: 新插入的结点，一定是插入在某个局部子树的根结点位置
int BST_Insert(BSTree &T, KeyType k) {
	// NOTE: 为新节点申请空间，第一个结点作为树根
	if (NULL == T) {
		// STEP: 为树根结点分配申请空间
		T = (BSTree) malloc(sizeof(BSTNode));

		// STEP: 根结点初始化
		T->key = k;
		T->lchild = T->rchild = NULL;

		// STEP: 代表插入成功
		return 1;
	} else if (k == T->key)
		// NOTE: 待插元素与“当前结点”值相同，不能插入！
		return 0;
	else if (k < T->key)
		// NOTE: 如果要插入的结点小于当前结点，进入左子树
		// 函数调用结束后，左孩子和原来的父亲会关联起来
		return BST_Insert(T->lchild, k);
	else
		// NOTE: 反之，进入右子树
		return BST_Insert(T->rchild, k);
}


// FUNCTION: 创建二叉排序树
// @param: str代表拟插入的结点值；n代表需要插入的结点个数
void Creat_BST(BSTree &T, KeyType str[], int n) {
	T = NULL;
	int i = 0;
	while (i < n) {
		// NOTE: 由BST_Insert完成实现插入操作
		BST_Insert(T, str[i]);
		i++;
	}
}


// FUNCTION: 中序遍历二叉排序树
void InOrder(BSTree T) {
	if (T != NULL) {
		InOrder(T->lchild);
		printf("%3d", T->key);
		InOrder(T->rchild);
	}
}


// FUNCTION: 在二叉排序树中，查找结点（非递归实现）
// HINT: 因为这里传入的T不是引用类型的，所以不必担心非递归算法对于T的改变，会影响主函数中T的值。
BSTNode *BST_Search(BSTree T, KeyType key) {
	while (T != NULL && key != T->key) {
		if (key < T->key) {
			// 当查找值比当前结点值小，让T指向左子树
			T = T->lchild;
		} else {
			// 当查找值比当前结点值大，让T指向右子树
			T = T->rchild;
		}
	}

	return T;
}


// FUNCTION: 在二叉排序树中，删除结点（递归实现）
void DeleteNode_BST(BSTree &root, KeyType x) {
	// NOTE: 如果树本来是空树，直接返回
	if (root == NULL) {
		return;
	}


	// NOTE: 树不为空，进一步讨论
	if (root->key > x) {
		DeleteNode_BST(root->lchild, x);
	} else if (root->key < x) {
		DeleteNode_BST(root->rchild, x);
	} else {
		if (root->lchild == NULL) {
			// STEP: 左子树为空。右子树直接顶上去
			// 申请一个临时变量tempNode，目的是一会要free
			BSTree tempNode = root;
			root = root->rchild;
			free(tempNode);
		} else if (root->rchild == NULL) {
			// STEP: 右子树为空。左子树直接顶上去
			BSTree tempNode = root; // 用临时指针tempNode指向root，方便待会删除
			root = root->lchild;
			free(tempNode);
		} else {
			// STEP: 左右子树都不为空。解决方法：左子树的最大结点or右子树的最小结点顶替。
			// ALERT: 下方代码以左子树最大结点来代替被删结点为例

			// STEP: 申请临时变量tempNode。使之指向待删结点root的左子树
			BSTree tempNode = root->lchild;


			// STEP: 找“左子树的最大结点”
			// HINT: 找“左子树最大结点”的方式：从待删结点的左子树根开始，一路往右，直到叶子结点为止。
			while (tempNode->rchild != NULL) {
				tempNode = tempNode->rchild;
			}

			// STEP: 将最大节点值覆盖待删结点值
			root->key = tempNode->key;

			// STEP: 将最大节点值覆盖待删结点值
			// HINT: 需要这一步的目的是：因为二叉排序树的各个结点务必保持各不一样。但经过上一步“将最大结点值覆盖待删结点值”后，必会使得树内两个结点值相等。但，我们也不能继续从待删结点处（结点root）开始删。因为这是我们刚刚赋值好的。否则程序就有问题了。所以，我们可以转化一下，（步进一步），从待删结点的左子树为起点开始递归——删除结点值为最大结点。
			// ALERT: 这一步也有一种简化办法。就是，找到最大结点的父节点。可以直接让最大结点父结点的右指针，直接指向最大结点的左孩子（就算左孩子为空也无妨，效果也是一样的）
			DeleteNode_BST(root->lchild, tempNode->key);
		}
	}
}


int main() {
	setbuf(stdout, NULL);


	// NOTE: Variable declaration
	// STEP: 声明二叉排序树
	BSTree T;

	// STEP: 声明用于存储父结点地址和用于查找的指针变量
	BSTree parent, search;

	// STEP: 将要插入二叉排序树的元素值
	KeyType str[] = {54, 20, 66, 40, 28, 89, 58};


	// NOTE: 验证中序遍历验证是否插入成功
	Creat_BST(T, str, 7);


	// NOTE: 中序遍历验证是否插入成功
	printf("Verification whether insert operation is success or not?\n");
	InOrder(T);
	printf("\n");


	// NOTE: 在二叉排序树中，查找结点
	search = BST_Search(T, 23);
	if (search) {
		printf("Node found! Its value is %d\n", search->key);
	} else {
		// 没找到search返回的是NULL
		printf("Ops! Node not found! \n");
	}


	// NOTE: 在二叉排序树中，删除结点
	DeleteNode_BST(T, 54);

	printf("Verification whether delete operation is success or not?\n");
	InOrder(T);
	printf("\n");

	return 0;
}